﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sokoban_Solver
{
    class Program
    {
        static void MegoldasKiir(List<Sokoban> mo)
        {
            char[] kar = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J','K','L','M','N','O','P','Q','R','S','T' };
            for (int i=mo.Count-1;i>=0;i--)
            {
                Console.Write("|{0}{1}| ", kar[mo[i].player.col], mo[i].player.row);
            }
            Console.WriteLine();
        }
        static void AddRow(int row, string line, int[,] map)
        {
            for (int i = 0; i < line.Length; i++)
            {
                map[row, i] = int.Parse(line.Substring(i, 1));
            }
        }
        static bool NodeAzonos(Sokoban egyik, Sokoban masik)
        {
            int azonos = 0;
            bool dobozok = false;
            bool jatekos = false;
            for (int i = 0; i<egyik.boxes.Count();i++)
            {                
                for (int m = 0; m < masik.boxes.Count(); m++)
                    if ((egyik.boxes[i].col == masik.boxes[m].col) && (egyik.boxes[i].row == masik.boxes[m].row))
                        azonos++;
            }
            if (azonos == egyik.boxes.Count())
                dobozok = true;
            if ((egyik.player.col == masik.player.col) && (egyik.player.row == masik.player.row))
                jatekos = true;
            return (dobozok && jatekos);
        }
        static bool IsThereDeadlock(Sokoban node)
        {            
            for (int i = 0; i<node.boxes.Count();i++)
            {
                int row = node.boxes[i].row;
                int col = node.boxes[i].col;
                if(!node.VanOttCel(row,col))
                {                    
                    if ((node.map[row-1,col]==0)&&(node.map[row,col+1]==0))
                        return true;
                    if ((node.map[row,col+1]==0)&&(node.map[row+1,col]==0))
                        return true;
                    if ((node.map[row+1,col]==0)&&(node.map[row,col-1]==0))
                        return true;
                    if ((node.map[row,col-1]==0)&&(node.map[row-1,col]==0))
                        return true;
                }
            }
            return false;
        }
        static Sokoban NodeMasolat(Sokoban masolni)
        {
            Sokoban m = new Sokoban();
            m.map = masolni.map;
            m.goals = masolni.goals;
            Point[] p = new Point[masolni.boxes.Count()];
            for (int i = 0; i < masolni.boxes.Count(); i++)
            {
                Point ptemp = new Point(masolni.boxes[i].row, masolni.boxes[i].col);
                p[i] = ptemp;                
            }
            m.boxes = p;
            m.maxCol = masolni.maxCol;
            m.maxRow = masolni.maxRow;
            m.melysegSzam = masolni.melysegSzam;
            m.parent = masolni.parent;
            m.player = new Point(masolni.player.row, masolni.player.col);
            return m;
        }        
        static void Main(string[] args)
        {
            List<Sokoban> nodes = new List<Sokoban>();
            List<Sokoban> done = new List<Sokoban>();
            List<Sokoban> megoldas = new List<Sokoban>();
            //0: fal, 1:szabad
            int playMap = 2;
            bool szelessegi = false;
            bool szelessegideadlock = false;            
            bool melysegi = false;
            bool melysegi2 = true;
            int melysegkorlat_step = 10;
            int melysegikorlat = 10;
            int melysegkorlat_max = 100;
            DateTime timer = new DateTime();
            timer = DateTime.Now;
            
            #region MAP 1 // 1. 8.706, 2. 8.754, 3. 0.31, 4. 0.427
            if (playMap == 1)
            {
                int maxRow = 9;
                int maxCol = 9;
                int[,] map = new int[maxRow, maxCol];
                AddRow(1, "000010000", map);
                AddRow(2, "000010000", map);
                AddRow(3, "000010000", map);
                AddRow(4, "011111110", map);
                AddRow(5, "000010000", map);
                AddRow(6, "000010000", map);
                AddRow(7, "000010000", map);
                Point player = new Point(4, 4);
                List<Point> goals = new List<Point>();
                goals.Add(new Point(1, 4));
                goals.Add(new Point(4, 1));
                goals.Add(new Point(4, 7));
                goals.Add(new Point(7, 4));
                List<Point> boxes = new List<Point>();
                boxes.Add(new Point(3, 4));
                boxes.Add(new Point(5, 4));
                boxes.Add(new Point(4, 3));
                boxes.Add(new Point(4, 5));
                Sokoban s = new Sokoban(maxRow, maxCol, map, player, boxes, goals, 0, null);
                nodes.Add(s);
                nodes[0].DrawMap();
            }
            #endregion
            #region MAP 2 // 1. 1.30.120, 2. 6.507, 3. 9.13, 4. 0.994
            if (playMap == 2)
            {
                int maxRow = 6;
                int maxCol = 8;
                int[,] map = new int[maxRow, maxCol];
                AddRow(0, "00000000", map);
                AddRow(1, "00011110", map);
                AddRow(2, "01111110", map);
                AddRow(3, "01111100", map);
                AddRow(4, "01100000", map);
                AddRow(5, "00000000", map);
                Point player = new Point(1, 4);
                List<Point> goals = new List<Point>();
                goals.Add(new Point(2, 4));
                goals.Add(new Point(2, 5));
                List<Point> boxes = new List<Point>();
                boxes.Add(new Point(2, 2));
                boxes.Add(new Point(3, 4));
                Sokoban s = new Sokoban(maxRow, maxCol, map, player, boxes, goals, 0, null);
                nodes.Add(s);
                nodes[0].DrawMap();
            }
            #endregion
            #region MAP 3
            if (playMap == 3)
            {
                int maxRow = 11;
                int maxCol = 11;
                int[,] map = new int[maxRow, maxCol];
                AddRow(0, "00000000000", map);
                AddRow(1, "01100001110", map);
                AddRow(2, "01111111110", map);
                AddRow(3, "01100000100", map);
                AddRow(4, "00101110100", map);
                AddRow(5, "00101111100", map);
                AddRow(6, "00100110100", map);
                AddRow(7, "00100100100", map);
                AddRow(8, "01111111100", map);
                AddRow(9, "01110110000", map);
                AddRow(10, "00000000000", map);
                Point player = new Point(6, 6);
                List<Point> goals = new List<Point>();
                goals.Add(new Point(4, 4));
                goals.Add(new Point(4, 5));
                goals.Add(new Point(4, 6));
                goals.Add(new Point(5, 4));
                List<Point> boxes = new List<Point>();
                boxes.Add(new Point(2, 6));
                boxes.Add(new Point(4, 2));
                boxes.Add(new Point(6, 8));
                boxes.Add(new Point(8, 4));
                Sokoban s = new Sokoban(maxRow, maxCol, map, player, boxes, goals, 0, null);
                nodes.Add(s);
                nodes[0].DrawMap();
            }
            #endregion

            //// Szélességi kereső
            #region SZKereso
            while ((szelessegi) && (nodes.Count > 0) && (!nodes[0].GoalState()))
            {
                if (done.Count % 100 == 0)
                    Console.Write(".");
                Sokoban s = new Sokoban();
                s = NodeMasolat(nodes[0]);
                if (s.Jobbra())
                {
                    int i = 0;
                    while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                        i++;
                    if (i == done.Count)
                    {
                        s.parent = nodes[0];
                        s.melysegSzam++;
                        nodes.Add(s);
                    }
                }
                s = NodeMasolat(nodes[0]);
                if (s.Balra())
                {
                    int i = 0;
                    while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                        i++;
                    if (i == done.Count)
                    {
                        s.parent = nodes[0];
                        s.melysegSzam++;
                        nodes.Add(s);
                    }
                }
                s = NodeMasolat(nodes[0]);
                if (s.Le())
                {
                    int i = 0;
                    while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                        i++;
                    if (i == done.Count)
                    {
                        s.parent = nodes[0];
                        s.melysegSzam++;
                        nodes.Add(s);
                    }
                }
                s = NodeMasolat(nodes[0]);
                if (s.Fel())
                {
                    int i = 0;
                    while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                        i++;
                    if (i == done.Count)
                    {
                        s.parent = nodes[0];
                        s.melysegSzam++;
                        nodes.Add(s);
                    }
                }

                done.Add(nodes[0]);
                nodes.RemoveAt(0);
            }
            if (szelessegi)
            Console.WriteLine("\n-- kész --");
            if (szelessegi)
                if (nodes.Count > 0)
                {
                    Sokoban elem = nodes[0];
                    while (elem != null)
                    {
                        megoldas.Add(elem);
                        elem = elem.parent;
                    }
                    MegoldasKiir(megoldas);
                    megoldas[0].DrawMap();
                }
                else
                    Console.WriteLine("Nincs megoldás");
            if (szelessegi)
            {
                Console.WriteLine("Nodes: {0} - Done: {1} - Steps: {2}", nodes.Count, done.Count, megoldas.Count);
                TimeSpan timediff = DateTime.Now.Subtract(timer);
                Console.WriteLine("Timer: {0}m {1}s {2}ms", timediff.Minutes, timediff.Seconds, timediff.Milliseconds);
            }
            #endregion

            //// Szélességi kereső Deadlock szűréssel
            #region SZKeresoWithDeadlockSense
            int deadlocks = 0;
            while ((szelessegideadlock) && (nodes.Count > 0) && (!nodes[0].GoalState()))
            {
                if (done.Count % 100 == 0)
                    Console.Write(".");
                if (!IsThereDeadlock(nodes[0]))
                {
                    Sokoban s = new Sokoban();
                    s = NodeMasolat(nodes[0]);
                    if (s.Jobbra())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[0]);
                    if (s.Balra())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[0]);
                    if (s.Le())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[0]);
                    if (s.Fel())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                }
                else
                    deadlocks++;
                done.Add(nodes[0]);
                nodes.RemoveAt(0);
            }
            if (szelessegideadlock)
            Console.WriteLine("\n-- kész --");
            if (szelessegideadlock)
                if (nodes.Count > 0)
                {
                    Sokoban elem = nodes[0];
                    while (elem != null)
                    {
                        megoldas.Add(elem);
                        elem = elem.parent;
                    }
                    MegoldasKiir(megoldas);
                    megoldas[0].DrawMap();
                }
                else
                    Console.WriteLine("Nincs megoldás");
            if (szelessegideadlock)
            {
                Console.WriteLine("Nodes: {0} - Done: {1} - Steps: {2} - Deadlocks: {3}", nodes.Count, done.Count, megoldas.Count, deadlocks);
                TimeSpan timediff = DateTime.Now.Subtract(timer);
                Console.WriteLine("Timer: {0}m {1}s {2}ms",timediff.Minutes,timediff.Seconds,timediff.Milliseconds);
            }
            #endregion

            //// Mélységi kereső    
            #region MeKereso
            while ((melysegi) && (nodes.Count > 0) && (!nodes[nodes.Count - 1].GoalState()))
            {
                int nodeelem = nodes.Count - 1;
                if (nodes[nodeelem].melysegSzam <= melysegkorlat_max)
                {
                    if (done.Count % 100 == 0)
                        Console.Write(".");
                    Sokoban s = new Sokoban();
                    s = NodeMasolat(nodes[nodeelem]);
                    if (s.Jobbra())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[nodeelem];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[nodeelem]);
                    if (s.Balra())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[nodeelem];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[nodeelem]);
                    if (s.Le())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[nodeelem];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[nodeelem]);
                    if (s.Fel())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[nodeelem];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    done.Add(nodes[nodeelem]);
                    nodes.RemoveAt(nodeelem);
                }
                else
                {
                    nodes.RemoveAt(nodeelem);
                }
            }
            if (melysegi)
            Console.WriteLine("\n-- kész --");
            if (melysegi)
                if (nodes.Count > 0)
                {
                    Sokoban elem = nodes[nodes.Count - 1];
                    while (elem != null)
                    {
                        megoldas.Add(elem);
                        elem = elem.parent;
                    }
                    MegoldasKiir(megoldas);
                    megoldas[0].DrawMap();
                }
                else
                    Console.WriteLine("Nincs megoldás");
            if (melysegi)
            {
                Console.WriteLine("Nodes: {0} - Done: {1} - Steps: {2}", nodes.Count, done.Count, megoldas.Count);
                TimeSpan timediff = DateTime.Now.Subtract(timer);
                Console.WriteLine("Timer: {0}m {1}s {2}ms", timediff.Minutes, timediff.Seconds, timediff.Milliseconds);
            }
            #endregion

            //// Mélységi kereső (iteratív mélyülés és Deadlock szűrés)
            #region MeKereso2
            deadlocks = 0;
            List<Sokoban> tooDeepNodes = new List<Sokoban>();
            bool notFound = true;
            while ((melysegi2) && (nodes.Count + tooDeepNodes.Count > 0)&&(notFound))
            {                
                if (done.Count % 100 == 0)
                    Console.Write(".");
                if (nodes.Count > 0)
                {
                    int nodeelem = nodes.Count - 1;
                    if (!nodes[nodeelem].GoalState())
                    {
                        if (!IsThereDeadlock(nodes[nodeelem]))
                        {
                            Sokoban s = new Sokoban();
                            s = NodeMasolat(nodes[nodeelem]);
                            if (s.Jobbra())
                            {
                                int i = 0;
                                while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                                    i++;
                                if (i == done.Count)
                                {
                                    s.parent = nodes[nodeelem];
                                    s.melysegSzam++;
                                    if (s.melysegSzam <= melysegikorlat)
                                        nodes.Add(s);
                                    else
                                        tooDeepNodes.Add(s);
                                }
                            }
                            s = NodeMasolat(nodes[nodeelem]);
                            if (s.Balra())
                            {
                                int i = 0;
                                while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                                    i++;
                                if (i == done.Count)
                                {
                                    s.parent = nodes[nodeelem];
                                    s.melysegSzam++;
                                    if (s.melysegSzam <= melysegikorlat)
                                        nodes.Add(s);
                                    else
                                        tooDeepNodes.Add(s);
                                }
                            }
                            s = NodeMasolat(nodes[nodeelem]);
                            if (s.Le())
                            {
                                int i = 0;
                                while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                                    i++;
                                if (i == done.Count)
                                {
                                    s.parent = nodes[nodeelem];
                                    s.melysegSzam++;
                                    if (s.melysegSzam <= melysegikorlat)
                                        nodes.Add(s);
                                    else
                                        tooDeepNodes.Add(s);
                                }
                            }
                            s = NodeMasolat(nodes[nodeelem]);
                            if (s.Fel())
                            {
                                int i = 0;
                                while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                                    i++;
                                if (i == done.Count)
                                {
                                    s.parent = nodes[nodeelem];
                                    s.melysegSzam++;
                                    if (s.melysegSzam <= melysegikorlat)
                                        nodes.Add(s);
                                    else
                                        tooDeepNodes.Add(s);
                                }
                            }
                            done.Add(nodes[nodeelem]);
                            nodes.RemoveAt(nodeelem);
                        }
                        else
                        {
                            deadlocks++;
                            done.Add(nodes[nodeelem]);
                            nodes.RemoveAt(nodeelem);
                        }
                    }
                    else
                        notFound = false;
                }
                else
                {
                    for (int i = 0; i < tooDeepNodes.Count; i++)
                    {
                        nodes.Add(tooDeepNodes[0]);
                        tooDeepNodes.RemoveAt(0);
                        if (melysegkorlat_step + melysegikorlat <= melysegkorlat_max)
                            melysegikorlat = melysegikorlat + melysegkorlat_step;
                        else
                            melysegikorlat = melysegkorlat_max;
                    }
                }
            }
        
            if (melysegi2)
                Console.WriteLine("\n-- kész --");
            if (melysegi2)
                if (nodes.Count > 0)
                {
                    Sokoban elem = nodes[nodes.Count - 1];
                    while (elem != null)
                    {
                        megoldas.Add(elem);
                        elem = elem.parent;
                    }
                    MegoldasKiir(megoldas);
                    megoldas[0].DrawMap();
                }
                else
                    Console.WriteLine("Nincs megoldás");
            if (melysegi2)
            {
                Console.WriteLine("Nodes: {0} - Done: {1} - Steps: {2} - Deadlocks: {3}", nodes.Count, done.Count, megoldas.Count,deadlocks);
                TimeSpan timediff = DateTime.Now.Subtract(timer);
                Console.WriteLine("Timer: {0}m {1}s {2}ms", timediff.Minutes, timediff.Seconds, timediff.Milliseconds);
            }
            #endregion
                        
            //// Szélességi kereső (Deadlock), de csak a dobozok (valid) mozgására
            #region SZKeresoWithDeadlockSense_OnlyPush
            deadlocks = 0;
            while ((szelessegideadlock) && (nodes.Count > 0) && (!nodes[0].GoalState()))
            {
                if (done.Count % 100 == 0)
                    Console.Write(".");
                if (!IsThereDeadlock(nodes[0]))
                {
                    Sokoban s = new Sokoban();
                    s = NodeMasolat(nodes[0]);
                    if (s.Jobbra())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[0]);
                    if (s.Balra())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[0]);
                    if (s.Le())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                    s = NodeMasolat(nodes[0]);
                    if (s.Fel())
                    {
                        int i = 0;
                        while ((i < done.Count) && (!NodeAzonos(done[i], s)))
                            i++;
                        if (i == done.Count)
                        {
                            s.parent = nodes[0];
                            s.melysegSzam++;
                            nodes.Add(s);
                        }
                    }
                }
                else
                    deadlocks++;
                done.Add(nodes[0]);
                nodes.RemoveAt(0);
            }
            if (szelessegideadlock)
                Console.WriteLine("\n-- kész --");
            if (szelessegideadlock)
                if (nodes.Count > 0)
                {
                    Sokoban elem = nodes[0];
                    while (elem != null)
                    {
                        megoldas.Add(elem);
                        elem = elem.parent;
                    }
                    MegoldasKiir(megoldas);
                    megoldas[0].DrawMap();
                }
                else
                    Console.WriteLine("Nincs megoldás");
            if (szelessegideadlock)
            {
                Console.WriteLine("Nodes: {0} - Done: {1} - Steps: {2} - Deadlocks: {3}", nodes.Count, done.Count, megoldas.Count, deadlocks);
                TimeSpan timediff = DateTime.Now.Subtract(timer);
                Console.WriteLine("Timer: {0}m {1}s {2}ms", timediff.Minutes, timediff.Seconds, timediff.Milliseconds);
            }
            #endregion
            Console.ReadLine();
        }

        // fffff
    }
}
